# source:https://leetcode.cn/problems/longest-repeating-character-replacement/ 滑窗
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        mx = 0
        ans = 0
        i = 0
        d = defaultdict(int)
        for j, v in enumerate(s):
            d[v] += 1
            mx = sorted(d.values())[-1]
            while j-i+1 - mx > k:
                d[s[i]] -= 1
                mx = sorted(d.values())[-1]
                i += 1
            ans = max(ans, j-i+1)
        return ans

# source:https://leetcode.cn/problems/the-k-strongest-values-in-an-array/ 双指针
class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        n = len(arr)
        mid = arr[n // 2 if n & 1 else n // 2 - 1]
        i, j = 0, n-1
        ans = []
        while k:
            t1 = abs(arr[i] - mid)
            t2 = abs(arr[j] - mid)
            if t1 == t2 or t2 > t1:
                ans.append(arr[j])
                j -= 1
            else:
                ans.append(arr[i])
                i += 1
            k -= 1
        return ans

# source: https://leetcode.cn/problems/bag-of-tokens/ 双指针
class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        tokens.sort()
        i, j = 0, len(tokens)-1
        ans, cnt = 0, 0
        while i <= j:
            if power < tokens[i] and ans < 1:
                break
            if power >= tokens[i]:
                power -= tokens[i]
                cnt += 1
                i += 1
            else:
                cnt -= 1
                power += tokens[j]
                j -= 1
            ans = max(ans, cnt)
        return ans